package com.LeeCode;


import java.util.Stack;

/**
 * 柱状图中最大的矩形
 */

public class Code084 {
    public static void main(String[] args) {
        int[] heights = {2, 4};
        System.out.println(new Code084().largestRectangleArea(heights));
    }

    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int index = stack.pop();
                int pre = stack.isEmpty() ? -1 : stack.peek();
                int area = heights[index] * (i - pre - 1);
                max = Math.max(max, area);
            }
            stack.push(i);
        }

        int end = heights.length; // 此时还在栈中的元素右边界肯定可以扩展到最右边
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int pre = stack.isEmpty() ? -1 : stack.peek();
            int area = heights[index] * (end - pre - 1);
            max = Math.max(max, area);
        }
        return max;
    }
}
